<!DOCTYPE html>
<html lang="zh">
    <head>
        <meta charset="utf-8">
        <meta http-equiv="X-UA-Compatible" content="IE=edge,chrome=1">
        <title>2021-02 YZU算法集训队第一次训练 | ChenDong Zhu&#39;s Blog</title><meta name="viewport" content="width=device-width, initial-scale=1.0">
<meta name="robots" content="noodp" />
<meta name="Description" content="YZU算法集训队第一次训练的题解"><link rel="prev" href="/2021/02/2021%E7%BE%8E%E8%B5%9B/" /><link rel="next" href="/2021/03/risc-v-%E6%9E%B6%E6%9E%84%E5%AD%A6%E4%B9%A0/" /><link rel="canonical" href="/2021/02/2021-02-yzu%E7%AE%97%E6%B3%95%E9%9B%86%E8%AE%AD%E9%98%9F%E7%AC%AC%E4%B8%80%E6%AC%A1%E8%AE%AD%E7%BB%83/" />
<link rel="shortcut icon" type="image/x-icon" href="/favicon.ico" />
<link rel="apple-touch-icon" sizes="180x180" href="/apple-touch-icon.png">
<link rel="icon" type="image/png" sizes="32x32" href="/favicon-32x32.png">
<link rel="icon" type="image/png" sizes="16x16" href="/favicon-16x16.png">
<link rel="manifest" href="/site.webmanifest">
<link rel="mask-icon" href="/safari-pinned-tab.svg" color="#5bbad5">
<meta name="msapplication-TileColor" content="#da532c">
<meta name="theme-color" content="#ffffff"><meta property="og:title" content="2021-02 YZU算法集训队第一次训练" />
<meta property="og:description" content="YZU算法集训队第一次训练的题解" />
<meta property="og:type" content="article" />
<meta property="og:url" content="/2021/02/2021-02-yzu%E7%AE%97%E6%B3%95%E9%9B%86%E8%AE%AD%E9%98%9F%E7%AC%AC%E4%B8%80%E6%AC%A1%E8%AE%AD%E7%BB%83/" /><meta property="article:section" content="posts" />
<meta property="article:published_time" content="2021-02-09T09:00:00+08:00" />
<meta property="article:modified_time" content="2020-02-09T09:00:00+08:00" />

<meta name="twitter:card" content="summary"/>
<meta name="twitter:title" content="2021-02 YZU算法集训队第一次训练"/>
<meta name="twitter:description" content="YZU算法集训队第一次训练的题解"/>
<script type="application/ld+json">
    {
        "@context": "http://schema.org",
        "@type": "BlogPosting",
        "headline": "2021-02 YZU算法集训队第一次训练",
        "mainEntityOfPage": {
            "@type": "WebPage",
            "@id": "\/2021\/02\/2021-02-yzu%E7%AE%97%E6%B3%95%E9%9B%86%E8%AE%AD%E9%98%9F%E7%AC%AC%E4%B8%80%E6%AC%A1%E8%AE%AD%E7%BB%83\/"
        },"image": {
                "@type": "ImageObject",
                "url": "\/cover.png",
                "width":  800 ,
                "height":  600 
            },"genre": "posts","keywords": "ACM","wordcount":  3152 ,
        "url": "\/2021\/02\/2021-02-yzu%E7%AE%97%E6%B3%95%E9%9B%86%E8%AE%AD%E9%98%9F%E7%AC%AC%E4%B8%80%E6%AC%A1%E8%AE%AD%E7%BB%83\/","datePublished": "2021-02-09T09:00:00\u002b08:00","dateModified": "2020-02-09T09:00:00\u002b08:00","license": "This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.","publisher": {
                "@type": "Organization",
                "name": "xxxx",
                "logo": {
                "@type": "ImageObject",
                "url": "\/logo.png",
                "width":  127 ,
                "height":  40 
                }
            },"description": "YZU算法集训队第一次训练的题解"
    }
    </script><link rel="stylesheet" href="/css/style.min.css"><link rel="stylesheet" href="/css/lib/fontawesome-free/all.min.css"><link rel="stylesheet" href="/css/lib/animate/animate.min.css"></head>
    <body><script>
            window.isDark = (window.localStorage && window.localStorage.getItem('theme')) === 'dark';
            window.isDark && document.body.classList.add('dark-theme');
        </script><div class="wrapper"><nav class="navbar">
    <div class="navbar-container">
        <div class="navbar-header animated bounceIn">
            <a href="/">ChenDong Zhu&#39;s Blog</a>
        </div>
        <div class="navbar-menu"><a class="menu-item" href="/posts" title="">文章</a><a class="menu-item" href="/tags" title="">标签</a><a class="menu-item" href="/categories" title="">分类</a><a class="menu-item" href="/about" title="">关于</a><a class="menu-item" href="https://hugo-loveit-en.netlify.com" title="English"><i class="fas fa-language fa-fw"></i></a><a href="javascript:void(0);" class="theme-switch"><i class="fas fa-adjust fa-rotate-180 fa-fw" title="切换主题"></i></a>
        </div>
    </div>
</nav><nav class="navbar-mobile">
    <div class="navbar-container">
        <div class="navbar-header">
            <div class="navbar-header-title animated bounceIn">
                <a href="/">ChenDong Zhu&#39;s Blog</a>
            </div>
            <div class="menu-toggle" id="menu-toggle">
                <span></span><span></span><span></span>
            </div>
        </div>
        <div class="navbar-menu" id="mobile-menu"><a class="menu-item" href="/posts" title="">文章</a><a class="menu-item" href="/tags" title="">标签</a><a class="menu-item" href="/categories" title="">分类</a><a class="menu-item" href="/about" title="">关于</a><a class="menu-item" href="https://hugo-loveit-en.netlify.com" title="English"></a><a href="javascript:void(0);" class="theme-switch"><i class="fas fa-adjust fa-rotate-180 fa-fw" title="切换主题"></i></a>
        </div>
    </div>
</nav><main class="main">
                <div class="container"><article class="page"><h1 class="post-title animated flipInX">2021-02 YZU算法集训队第一次训练</h1><div class="post-meta">
            <div class="post-meta-main"><a class="author" href="/" rel="author" target="_blank">
                    <i class="fas fa-user-circle fa-fw"></i>ChenDong Zhu
                </a>&nbsp;<span class="post-category">收录于&nbsp;<i class="far fa-folder fa-fw"></i><a href="/categories/acm/">Acm</a>&nbsp;</span></div>
            <div class="post-meta-other"><i class="far fa-calendar-alt fa-fw"></i><time datetime=2021-02-09>2021-02-09</time>&nbsp;
                <i class="fas fa-pencil-alt fa-fw"></i>约 3152 字&nbsp;
                <i class="far fa-clock fa-fw"></i>预计阅读 7 分钟&nbsp;</div>
        </div><div class="post-toc" id="post-toc">
                <h2 class="post-toc-title">目录</h2>
                <div class="post-toc-content"><nav id="TableOfContents">
  <ul>
    <li><a href="#problem-a---biathlon-track">Problem A - Biathlon Track</a>
      <ul>
        <li>
          <ul>
            <li><a href="#step-1-枚举矩形上界和下界所在的行-on2">STEP 1 枚举矩形上界和下界所在的行—— $O(N^2)$</a></li>
            <li><a href="#step-2-在第一步的枚举中从左往右枚举矩形右边界同时寻找最优的左边界onlogn">STEP 2 在第一步的枚举中，从左往右枚举矩形右边界，同时寻找最优的左边界——$O(NlogN)$</a></li>
            <li><a href="#举例子">举例子</a></li>
            <li><a href="#你是不是很困惑为啥放入set的数值如此奇怪">你是不是很困惑，为啥放入Set的数值如此奇怪？</a></li>
          </ul>
        </li>
      </ul>
    </li>
    <li><a href="#problem-c---gukiz-hates-boxes">Problem C - GukiZ hates Boxes</a></li>
    <li><a href="#problem-h---coffee-break">Problem H - Coffee Break</a></li>
  </ul>
</nav></div>
            </div>
            <div class="post-toc-mobile" id="post-toc-mobile">
                <details>
                    <summary>
                        <div class="post-toc-title">
                            <span>目录</span>
                            <span><i class="details icon fas fa-angle-down"></i></span>
                        </div>
                    </summary>
                    <div class="post-toc-content"><nav id="TableOfContentsMobile">
  <ul>
    <li><a href="#problem-a---biathlon-track">Problem A - Biathlon Track</a>
      <ul>
        <li>
          <ul>
            <li><a href="#step-1-枚举矩形上界和下界所在的行-on2">STEP 1 枚举矩形上界和下界所在的行—— $O(N^2)$</a></li>
            <li><a href="#step-2-在第一步的枚举中从左往右枚举矩形右边界同时寻找最优的左边界onlogn">STEP 2 在第一步的枚举中，从左往右枚举矩形右边界，同时寻找最优的左边界——$O(NlogN)$</a></li>
            <li><a href="#举例子">举例子</a></li>
            <li><a href="#你是不是很困惑为啥放入set的数值如此奇怪">你是不是很困惑，为啥放入Set的数值如此奇怪？</a></li>
          </ul>
        </li>
      </ul>
    </li>
    <li><a href="#problem-c---gukiz-hates-boxes">Problem C - GukiZ hates Boxes</a></li>
    <li><a href="#problem-h---coffee-break">Problem H - Coffee Break</a></li>
  </ul>
</nav></div>
                </details>
            </div><div class="post-content"><a class="post-dummy-target" id="problem-a---biathlon-track"></a><h2>Problem A - Biathlon Track</h2>
<p>最小时间复杂度$N^3Log(N)$。</p>
<a class="post-dummy-target" id="step-1-枚举矩形上界和下界所在的行-on2"></a><h4>STEP 1 枚举矩形上界和下界所在的行—— $O(N^2)$</h4>
<p>通过两个for循环枚举矩形的上界和下界。</p>
<a class="post-dummy-target" id="step-2-在第一步的枚举中从左往右枚举矩形右边界同时寻找最优的左边界onlogn"></a><h4>STEP 2 在第一步的枚举中，从左往右枚举矩形右边界，同时寻找最优的左边界——$O(NlogN)$</h4>
<p>枚举需要$N$的时间复杂度，每次枚举右边界需要使用c++的set容器的lower_bound()函数，所以是$O(NlogN)$.</p>
<a class="post-dummy-target" id="举例子"></a><h4>举例子</h4>
<p>我们以第$i$行作为矩形的上界，以第j行作为矩形的下界。</p>
<ul>
<li>先将第一列从下往上走的总时间放入Set，然后从第三列开始，使用lower_bound()函数查找set中能让整个矩形最接近所给时间的数值（此时set中只有1个数）</li>
<li>再将<font color='red'>第二列从下往上走的总时间减去上界第一列到第二列的时间和下界限第二列到第一列的时间</font>，放入Set，枚举第四列作为右边界，使用lower_bound()函数查找set中能让整个矩形最接近所给时间的数值。</li>
<li>&hellip;&hellip;</li>
<li>将第k-2列从下往上走的总时间减去上界第一列到第k-2列的时间和下界限第k-2列到第一列的时间，放入set，枚举第k列作为右边界，使用lower_bound()函数查找set中能让整个矩形最接近所给时间的数值。</li>
</ul>
<a class="post-dummy-target" id="你是不是很困惑为啥放入set的数值如此奇怪"></a><h4>你是不是很困惑，为啥放入Set的数值如此奇怪？</h4>
<p>原因是，我们枚举的时候并不是用给定时间$t$减去右边界的时间，然后去找左边界，因为这样还是$N^4$。</p>
<p>我们枚举的时候，用的是从第一列到枚举的那一列，然后从那一列往下走，再从枚举的那一列往左走到第一列。用图表示为：(以样例数据，上界为1，下界为3，枚举到第6列为例)</p>
<p><figure><img src="/svg/loading.min.svg" data-sizes="auto" data-src="/images/ACM/ACM_Train_1.png" alt="枚举" class="lazyload"><figcaption class="image-caption">枚举</figcaption></figure></p>
<p>给定的时间是48，紫色的时间是45，我们在set中要找一个最接近48-45=3的时间，现在Set中有一下数据：</p>
<p><figure><img src="/svg/loading.min.svg" data-sizes="auto" data-src="/images/ACM/ACM_Train_2.png" alt="Set中已有的数" class="lazyload"><figcaption class="image-caption">Set中已有的数</figcaption></figure></p>
<p>Set中已有{4，4，-12}再加上本次枚举放入的-12，最接近3的是4，那么此时，此时一圈与给定时间的偏差为1，如果比之前所有数据要好，那么我们存储最上界，最下界，和此时的右边界。</p>
<p>放入Set的时间复杂度是$log(N)$，取出来也是$log(N)$。具体实现找Set中最近，可能需要用到两次lower_bound,比如set中有{1，3，9，11}，我们要找5，lower_bound()出来是3，（它返回第一个小于5的数）,但是我们要确保大于5不会有更接近的数，那么我们要再lower_bound(5+(5-3))，5-3是相差的值，如果在这个相差的值能存在大于5小于5+（5-3）的数，说明存在一个大于5且更接近5的数。</p>
<p>最后我们用$O(N)$的时间遍历一遍左边界，看看它是在哪里达到这个最优值的（因为我们只能从Set中获取达到最优的时间，而无法获取达到最优是哪条左边界）</p>
<p>以下是错误代码！</p>
<p>以下是错误代码！</p>
<p>以下是错误代码！</p>
<div class="highlight"><div class="chroma">
<table class="lntable"><tr><td class="lntd">
<pre tabindex="0" class="chroma"><code><span class="lnt">  1
</span><span class="lnt">  2
</span><span class="lnt">  3
</span><span class="lnt">  4
</span><span class="lnt">  5
</span><span class="lnt">  6
</span><span class="lnt">  7
</span><span class="lnt">  8
</span><span class="lnt">  9
</span><span class="lnt"> 10
</span><span class="lnt"> 11
</span><span class="lnt"> 12
</span><span class="lnt"> 13
</span><span class="lnt"> 14
</span><span class="lnt"> 15
</span><span class="lnt"> 16
</span><span class="lnt"> 17
</span><span class="lnt"> 18
</span><span class="lnt"> 19
</span><span class="lnt"> 20
</span><span class="lnt"> 21
</span><span class="lnt"> 22
</span><span class="lnt"> 23
</span><span class="lnt"> 24
</span><span class="lnt"> 25
</span><span class="lnt"> 26
</span><span class="lnt"> 27
</span><span class="lnt"> 28
</span><span class="lnt"> 29
</span><span class="lnt"> 30
</span><span class="lnt"> 31
</span><span class="lnt"> 32
</span><span class="lnt"> 33
</span><span class="lnt"> 34
</span><span class="lnt"> 35
</span><span class="lnt"> 36
</span><span class="lnt"> 37
</span><span class="lnt"> 38
</span><span class="lnt"> 39
</span><span class="lnt"> 40
</span><span class="lnt"> 41
</span><span class="lnt"> 42
</span><span class="lnt"> 43
</span><span class="lnt"> 44
</span><span class="lnt"> 45
</span><span class="lnt"> 46
</span><span class="lnt"> 47
</span><span class="lnt"> 48
</span><span class="lnt"> 49
</span><span class="lnt"> 50
</span><span class="lnt"> 51
</span><span class="lnt"> 52
</span><span class="lnt"> 53
</span><span class="lnt"> 54
</span><span class="lnt"> 55
</span><span class="lnt"> 56
</span><span class="lnt"> 57
</span><span class="lnt"> 58
</span><span class="lnt"> 59
</span><span class="lnt"> 60
</span><span class="lnt"> 61
</span><span class="lnt"> 62
</span><span class="lnt"> 63
</span><span class="lnt"> 64
</span><span class="lnt"> 65
</span><span class="lnt"> 66
</span><span class="lnt"> 67
</span><span class="lnt"> 68
</span><span class="lnt"> 69
</span><span class="lnt"> 70
</span><span class="lnt"> 71
</span><span class="lnt"> 72
</span><span class="lnt"> 73
</span><span class="lnt"> 74
</span><span class="lnt"> 75
</span><span class="lnt"> 76
</span><span class="lnt"> 77
</span><span class="lnt"> 78
</span><span class="lnt"> 79
</span><span class="lnt"> 80
</span><span class="lnt"> 81
</span><span class="lnt"> 82
</span><span class="lnt"> 83
</span><span class="lnt"> 84
</span><span class="lnt"> 85
</span><span class="lnt"> 86
</span><span class="lnt"> 87
</span><span class="lnt"> 88
</span><span class="lnt"> 89
</span><span class="lnt"> 90
</span><span class="lnt"> 91
</span><span class="lnt"> 92
</span><span class="lnt"> 93
</span><span class="lnt"> 94
</span><span class="lnt"> 95
</span><span class="lnt"> 96
</span><span class="lnt"> 97
</span><span class="lnt"> 98
</span><span class="lnt"> 99
</span><span class="lnt">100
</span><span class="lnt">101
</span><span class="lnt">102
</span><span class="lnt">103
</span><span class="lnt">104
</span><span class="lnt">105
</span><span class="lnt">106
</span><span class="lnt">107
</span><span class="lnt">108
</span><span class="lnt">109
</span><span class="lnt">110
</span><span class="lnt">111
</span><span class="lnt">112
</span><span class="lnt">113
</span><span class="lnt">114
</span><span class="lnt">115
</span><span class="lnt">116
</span><span class="lnt">117
</span><span class="lnt">118
</span><span class="lnt">119
</span><span class="lnt">120
</span><span class="lnt">121
</span><span class="lnt">122
</span><span class="lnt">123
</span><span class="lnt">124
</span><span class="lnt">125
</span><span class="lnt">126
</span><span class="lnt">127
</span><span class="lnt">128
</span><span class="lnt">129
</span><span class="lnt">130
</span><span class="lnt">131
</span><span class="lnt">132
</span><span class="lnt">133
</span><span class="lnt">134
</span><span class="lnt">135
</span><span class="lnt">136
</span><span class="lnt">137
</span></code></pre></td>
<td class="lntd">
<pre tabindex="0" class="chroma"><code class="language-c++" data-lang="c++"><span class="cp">#include</span> <span class="cpf">&lt;iostream&gt;</span><span class="cp">
</span><span class="cp"></span><span class="k">using</span> <span class="k">namespace</span> <span class="n">std</span><span class="p">;</span>

<span class="kt">int</span> <span class="n">plot</span><span class="p">[</span><span class="mi">303</span><span class="p">][</span><span class="mi">303</span><span class="p">];</span>			<span class="c1">// 整个滑雪平面高度的数组
</span><span class="c1"></span><span class="kt">int</span> <span class="n">tp</span><span class="p">,</span> <span class="n">tu</span><span class="p">,</span> <span class="n">td</span><span class="p">;</span>			<span class="c1">// 时间
</span><span class="c1"></span><span class="kt">int</span> <span class="n">m</span><span class="p">,</span><span class="n">n</span><span class="p">,</span><span class="n">t</span><span class="p">;</span>				<span class="c1">// 行数，列数，时间
</span><span class="c1">// 枚举每个左上角，与宽度，二分查找长度
</span><span class="c1">// 前缀和预处理时间
</span><span class="c1"></span><span class="kt">int</span> <span class="n">r</span><span class="p">[</span><span class="mi">303</span><span class="p">][</span><span class="mi">303</span><span class="p">];</span>		<span class="c1">// 往右走时间前缀和
</span><span class="c1"></span><span class="kt">int</span> <span class="n">d</span><span class="p">[</span><span class="mi">303</span><span class="p">][</span><span class="mi">303</span><span class="p">];</span>			<span class="c1">// 向下走时间前缀和
</span><span class="c1"></span><span class="kt">int</span> <span class="n">l</span><span class="p">[</span><span class="mi">303</span><span class="p">][</span><span class="mi">303</span><span class="p">];</span>			<span class="c1">// 往左走时间前缀和
</span><span class="c1"></span><span class="kt">int</span> <span class="n">u</span><span class="p">[</span><span class="mi">303</span><span class="p">][</span><span class="mi">303</span><span class="p">];</span>			<span class="c1">// 往上走时间前缀和
</span><span class="c1"></span>

<span class="kt">int</span> <span class="nf">getDis</span><span class="p">(</span><span class="kt">int</span> <span class="n">ans</span><span class="p">,</span> <span class="kt">int</span> <span class="n">t</span><span class="p">)</span> <span class="p">{</span>
	<span class="k">if</span><span class="p">(</span><span class="n">ans</span> <span class="o">&gt;</span> <span class="n">t</span><span class="p">)</span> <span class="k">return</span> <span class="n">ans</span> <span class="o">-</span><span class="n">t</span><span class="p">;</span>
	<span class="k">else</span> <span class="k">return</span> <span class="n">t</span><span class="o">-</span><span class="n">ans</span><span class="p">;</span>
<span class="p">}</span>

<span class="kt">int</span> <span class="nf">getAns</span><span class="p">(</span><span class="kt">int</span> <span class="n">ulx</span><span class="p">,</span> <span class="kt">int</span> <span class="n">uly</span><span class="p">,</span> <span class="kt">int</span> <span class="n">drx</span><span class="p">,</span> <span class="kt">int</span> <span class="n">dry</span><span class="p">)</span> <span class="p">{</span>
	<span class="k">return</span> <span class="p">(</span><span class="n">r</span><span class="p">[</span><span class="n">ulx</span><span class="p">][</span><span class="n">dry</span><span class="p">]</span> <span class="o">-</span> <span class="n">r</span><span class="p">[</span><span class="n">ulx</span><span class="p">][</span><span class="n">uly</span><span class="p">]</span> <span class="o">+</span> <span class="n">d</span><span class="p">[</span><span class="n">drx</span><span class="p">][</span><span class="n">dry</span><span class="p">]</span> <span class="o">-</span> <span class="n">d</span><span class="p">[</span><span class="n">ulx</span><span class="p">][</span><span class="n">dry</span><span class="p">]</span> <span class="o">+</span> <span class="n">l</span><span class="p">[</span><span class="n">drx</span><span class="p">][</span><span class="n">uly</span><span class="p">]</span> <span class="o">-</span> <span class="n">l</span><span class="p">[</span><span class="n">drx</span><span class="p">][</span><span class="n">dry</span><span class="p">]</span> <span class="o">+</span> <span class="n">u</span><span class="p">[</span><span class="n">ulx</span><span class="p">][</span><span class="n">uly</span><span class="p">]</span> <span class="o">-</span> <span class="n">u</span><span class="p">[</span><span class="n">drx</span><span class="p">][</span><span class="n">uly</span><span class="p">]);</span>
<span class="p">}</span>

<span class="kt">int</span> <span class="nf">main</span><span class="p">()</span> <span class="p">{</span>
	<span class="n">cin</span> <span class="o">&gt;&gt;</span> <span class="n">m</span> <span class="o">&gt;&gt;</span> <span class="n">n</span> <span class="o">&gt;&gt;</span> <span class="n">t</span><span class="p">;</span>
	<span class="n">cin</span> <span class="o">&gt;&gt;</span> <span class="n">tp</span> <span class="o">&gt;&gt;</span> <span class="n">tu</span> <span class="o">&gt;&gt;</span> <span class="n">td</span><span class="p">;</span>
	<span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">1</span><span class="p">;</span> <span class="n">i</span> <span class="o">&lt;=</span> <span class="n">m</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="p">{</span>
		<span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">j</span> <span class="o">=</span> <span class="mi">1</span><span class="p">;</span> <span class="n">j</span> <span class="o">&lt;=</span> <span class="n">n</span><span class="p">;</span> <span class="n">j</span><span class="o">++</span><span class="p">)</span> <span class="p">{</span>
			<span class="n">cin</span> <span class="o">&gt;&gt;</span> <span class="n">plot</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="n">j</span><span class="p">];</span>
		<span class="p">}</span>
	<span class="p">}</span>
	<span class="c1">// 预处理时间前缀和
</span><span class="c1"></span>	<span class="c1">// 往右走
</span><span class="c1"></span>	<span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">1</span><span class="p">;</span> <span class="n">i</span> <span class="o">&lt;=</span> <span class="n">m</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="p">{</span>
		<span class="n">r</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="mi">1</span><span class="p">]</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span>
		<span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">j</span> <span class="o">=</span> <span class="mi">2</span><span class="p">;</span> <span class="n">j</span> <span class="o">&lt;=</span> <span class="n">n</span><span class="p">;</span> <span class="n">j</span><span class="o">++</span><span class="p">)</span> <span class="p">{</span>
			<span class="k">if</span><span class="p">(</span><span class="n">plot</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="n">j</span><span class="p">]</span> <span class="o">&lt;</span> <span class="n">plot</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="n">j</span><span class="o">-</span><span class="mi">1</span><span class="p">])</span> <span class="n">r</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="n">j</span><span class="p">]</span> <span class="o">=</span> <span class="n">r</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="n">j</span><span class="o">-</span><span class="mi">1</span><span class="p">]</span><span class="o">+</span><span class="n">td</span><span class="p">;</span>			<span class="c1">// 下降
</span><span class="c1"></span>			<span class="k">else</span> <span class="k">if</span><span class="p">(</span><span class="n">plot</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="n">j</span><span class="p">]</span> <span class="o">==</span> <span class="n">plot</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="n">j</span><span class="o">-</span><span class="mi">1</span><span class="p">])</span> <span class="n">r</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="n">j</span><span class="p">]</span> <span class="o">=</span> <span class="n">r</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="n">j</span><span class="o">-</span><span class="mi">1</span><span class="p">]</span><span class="o">+</span><span class="n">tp</span><span class="p">;</span>		<span class="c1">// 平
</span><span class="c1"></span>			<span class="k">else</span> <span class="n">r</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="n">j</span><span class="p">]</span> <span class="o">=</span> <span class="n">r</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="n">j</span><span class="o">-</span><span class="mi">1</span><span class="p">]</span><span class="o">+</span><span class="n">tu</span><span class="p">;</span>									<span class="c1">// 上升
</span><span class="c1"></span>		<span class="p">}</span>
	<span class="p">}</span>
	<span class="c1">// 往下走
</span><span class="c1"></span>	<span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">j</span> <span class="o">=</span> <span class="mi">1</span><span class="p">;</span> <span class="n">j</span> <span class="o">&lt;=</span> <span class="n">n</span><span class="p">;</span> <span class="n">j</span><span class="o">++</span><span class="p">)</span> <span class="p">{</span>
		<span class="n">d</span><span class="p">[</span><span class="mi">1</span><span class="p">][</span><span class="n">j</span><span class="p">]</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span>
		<span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">2</span><span class="p">;</span> <span class="n">i</span> <span class="o">&lt;=</span> <span class="n">m</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="p">{</span>
			<span class="k">if</span><span class="p">(</span><span class="n">plot</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="n">j</span><span class="p">]</span> <span class="o">&lt;</span> <span class="n">plot</span><span class="p">[</span><span class="n">i</span><span class="o">-</span><span class="mi">1</span><span class="p">][</span><span class="n">j</span><span class="p">])</span> <span class="n">d</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="n">j</span><span class="p">]</span> <span class="o">=</span> <span class="n">d</span><span class="p">[</span><span class="n">i</span><span class="o">-</span><span class="mi">1</span><span class="p">][</span><span class="n">j</span><span class="p">]</span> <span class="o">+</span> <span class="n">td</span><span class="p">;</span>
			<span class="k">else</span> <span class="k">if</span><span class="p">(</span><span class="n">plot</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="n">j</span><span class="p">]</span> <span class="o">==</span> <span class="n">plot</span><span class="p">[</span><span class="n">i</span><span class="o">-</span><span class="mi">1</span><span class="p">][</span><span class="n">j</span><span class="p">])</span> <span class="n">d</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="n">j</span><span class="p">]</span> <span class="o">=</span> <span class="n">d</span><span class="p">[</span><span class="n">i</span><span class="o">-</span><span class="mi">1</span><span class="p">][</span><span class="n">j</span><span class="p">]</span> <span class="o">+</span> <span class="n">tp</span><span class="p">;</span>
			<span class="k">else</span> <span class="n">d</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="n">j</span><span class="p">]</span> <span class="o">=</span> <span class="n">d</span><span class="p">[</span><span class="n">i</span><span class="o">-</span><span class="mi">1</span><span class="p">][</span><span class="n">j</span><span class="p">]</span> <span class="o">+</span> <span class="n">tu</span><span class="p">;</span>
		<span class="p">}</span>
	<span class="p">}</span>
	<span class="c1">// 往左走
</span><span class="c1"></span>	<span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">1</span><span class="p">;</span> <span class="n">i</span> <span class="o">&lt;=</span> <span class="n">m</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="p">{</span>
		<span class="n">l</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="n">n</span><span class="p">]</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span>
		<span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">j</span> <span class="o">=</span> <span class="n">n</span><span class="o">-</span><span class="mi">1</span><span class="p">;</span> <span class="n">j</span> <span class="o">&gt;=</span> <span class="mi">1</span><span class="p">;</span> <span class="n">j</span><span class="o">--</span><span class="p">)</span> <span class="p">{</span>
			<span class="k">if</span><span class="p">(</span><span class="n">plot</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="n">j</span><span class="p">]</span> <span class="o">&lt;</span> <span class="n">plot</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="n">j</span><span class="o">+</span><span class="mi">1</span><span class="p">])</span> <span class="n">l</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="n">j</span><span class="p">]</span> <span class="o">=</span> <span class="n">l</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="n">j</span><span class="o">+</span><span class="mi">1</span><span class="p">]</span> <span class="o">+</span> <span class="n">td</span><span class="p">;</span>
			<span class="k">else</span> <span class="k">if</span><span class="p">(</span><span class="n">plot</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="n">j</span><span class="p">]</span> <span class="o">==</span> <span class="n">plot</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="n">j</span><span class="o">+</span><span class="mi">1</span><span class="p">])</span> <span class="n">l</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="n">j</span><span class="p">]</span> <span class="o">=</span> <span class="n">l</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="n">j</span><span class="o">+</span><span class="mi">1</span><span class="p">]</span> <span class="o">+</span> <span class="n">tp</span><span class="p">;</span>
			<span class="k">else</span> <span class="n">l</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="n">j</span><span class="p">]</span> <span class="o">=</span> <span class="n">l</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="n">j</span><span class="o">+</span><span class="mi">1</span><span class="p">]</span> <span class="o">+</span> <span class="n">tu</span><span class="p">;</span>
		<span class="p">}</span>
	<span class="p">}</span>
	<span class="c1">// 往上走
</span><span class="c1"></span>	<span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">j</span> <span class="o">=</span> <span class="mi">1</span><span class="p">;</span> <span class="n">j</span> <span class="o">&lt;=</span> <span class="n">n</span><span class="p">;</span> <span class="n">j</span><span class="o">++</span><span class="p">)</span> <span class="p">{</span>
		<span class="n">u</span><span class="p">[</span><span class="n">m</span><span class="p">][</span><span class="n">j</span><span class="p">]</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span>
		<span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="n">m</span><span class="o">-</span><span class="mi">1</span><span class="p">;</span> <span class="n">i</span> <span class="o">&gt;=</span> <span class="mi">1</span><span class="p">;</span> <span class="n">i</span><span class="o">--</span><span class="p">)</span> <span class="p">{</span>
			<span class="k">if</span><span class="p">(</span><span class="n">plot</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="n">j</span><span class="p">]</span> <span class="o">&lt;</span> <span class="n">plot</span><span class="p">[</span><span class="n">i</span><span class="o">+</span><span class="mi">1</span><span class="p">][</span><span class="n">j</span><span class="p">])</span> <span class="n">u</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="n">j</span><span class="p">]</span> <span class="o">=</span> <span class="n">u</span><span class="p">[</span><span class="n">i</span><span class="o">+</span><span class="mi">1</span><span class="p">][</span><span class="n">j</span><span class="p">]</span> <span class="o">+</span> <span class="n">td</span><span class="p">;</span>
			<span class="k">else</span> <span class="k">if</span><span class="p">(</span><span class="n">plot</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="n">j</span><span class="p">]</span> <span class="o">==</span> <span class="n">plot</span><span class="p">[</span><span class="n">i</span><span class="o">+</span><span class="mi">1</span><span class="p">][</span><span class="n">j</span><span class="p">])</span> <span class="n">u</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="n">j</span><span class="p">]</span> <span class="o">=</span> <span class="n">u</span><span class="p">[</span><span class="n">i</span><span class="o">+</span><span class="mi">1</span><span class="p">][</span><span class="n">j</span><span class="p">]</span> <span class="o">+</span> <span class="n">tp</span><span class="p">;</span>
			<span class="k">else</span> <span class="n">u</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="n">j</span><span class="p">]</span> <span class="o">=</span> <span class="n">u</span><span class="p">[</span><span class="n">i</span><span class="o">+</span><span class="mi">1</span><span class="p">][</span><span class="n">j</span><span class="p">]</span> <span class="o">+</span> <span class="n">tu</span><span class="p">;</span> 
		<span class="p">}</span>
	<span class="p">}</span>

	<span class="c1">// test 4 3 6 7
</span><span class="c1"></span>	<span class="c1">// cout &lt;&lt; (r[4][7]-r[4][3])+(d[6][7]-d[4][7])+(l[6][3]-l[6][7])+(u[4][3]-u[6][3]);
</span><span class="c1"></span>	<span class="kt">int</span> <span class="n">ulx</span><span class="p">,</span> <span class="n">uly</span><span class="p">,</span> <span class="n">drx</span><span class="p">,</span> <span class="n">dry</span><span class="p">;</span>		<span class="c1">// 存储最接近答案的节点
</span><span class="c1"></span>	<span class="kt">int</span> <span class="n">dis</span><span class="p">;</span>
	<span class="c1">// 先构建一个答案
</span><span class="c1"></span>	<span class="n">ulx</span> <span class="o">=</span> <span class="n">uly</span> <span class="o">=</span> <span class="mi">1</span><span class="p">;</span>
	<span class="n">drx</span> <span class="o">=</span> <span class="n">m</span><span class="p">;</span>
	<span class="n">dry</span> <span class="o">=</span> <span class="n">n</span><span class="p">;</span>
	<span class="n">dis</span> <span class="o">=</span> <span class="n">getDis</span><span class="p">(</span><span class="n">getAns</span><span class="p">(</span><span class="n">ulx</span><span class="p">,</span><span class="n">uly</span><span class="p">,</span><span class="n">drx</span><span class="p">,</span><span class="n">dry</span><span class="p">),</span><span class="n">t</span><span class="p">);</span>

	<span class="c1">// 枚举左上的点
</span><span class="c1"></span>	<span class="k">if</span><span class="p">(</span><span class="nb">true</span><span class="p">)</span> <span class="p">{</span>		<span class="c1">// 按行
</span><span class="c1"></span>		<span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">1</span><span class="p">;</span> <span class="n">i</span> <span class="o">&lt;=</span> <span class="n">m</span><span class="o">-</span><span class="mi">2</span> <span class="p">;</span><span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="p">{</span>
			<span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">j</span> <span class="o">=</span> <span class="mi">1</span><span class="p">;</span> <span class="n">j</span> <span class="o">&lt;=</span> <span class="n">n</span><span class="o">-</span><span class="mi">2</span><span class="p">;</span> <span class="n">j</span><span class="o">++</span><span class="p">)</span> <span class="p">{</span>
				<span class="c1">// 求右下的点为第k行时候的答案
</span><span class="c1"></span>				<span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">k</span> <span class="o">=</span> <span class="n">i</span><span class="o">+</span><span class="mi">2</span><span class="p">;</span> <span class="n">k</span> <span class="o">&lt;=</span> <span class="n">m</span><span class="p">;</span> <span class="n">k</span><span class="o">++</span><span class="p">)</span> <span class="p">{</span>
					<span class="kt">int</span> <span class="n">ql</span> <span class="o">=</span> <span class="n">j</span> <span class="o">+</span> <span class="mi">2</span><span class="p">;</span>
					<span class="kt">int</span> <span class="n">qr</span> <span class="o">=</span> <span class="n">n</span><span class="p">;</span>
					<span class="k">if</span><span class="p">(</span><span class="n">getAns</span><span class="p">(</span><span class="n">i</span><span class="p">,</span><span class="n">j</span><span class="p">,</span><span class="n">k</span><span class="p">,</span><span class="n">ql</span><span class="p">)</span> <span class="o">&gt;</span> <span class="n">t</span><span class="p">)</span> <span class="p">{</span>
						<span class="k">if</span><span class="p">(</span><span class="n">getDis</span><span class="p">(</span><span class="n">getAns</span><span class="p">(</span><span class="n">i</span><span class="p">,</span><span class="n">j</span><span class="p">,</span><span class="n">k</span><span class="p">,</span><span class="n">ql</span><span class="p">),</span><span class="n">t</span><span class="p">)</span> <span class="o">&lt;</span> <span class="n">dis</span><span class="p">)</span> <span class="p">{</span>	<span class="c1">// 更新答案
</span><span class="c1"></span>							<span class="n">ulx</span> <span class="o">=</span> <span class="n">i</span><span class="p">;</span>
							<span class="n">uly</span> <span class="o">=</span> <span class="n">j</span><span class="p">;</span> 
							<span class="n">drx</span> <span class="o">=</span> <span class="n">k</span><span class="p">;</span>
							<span class="n">dry</span> <span class="o">=</span> <span class="n">ql</span><span class="p">;</span>
							<span class="n">dis</span> <span class="o">=</span> <span class="n">getDis</span><span class="p">(</span><span class="n">getAns</span><span class="p">(</span><span class="n">i</span><span class="p">,</span><span class="n">j</span><span class="p">,</span><span class="n">k</span><span class="p">,</span><span class="n">ql</span><span class="p">),</span><span class="n">t</span><span class="p">);</span>
							<span class="k">continue</span><span class="p">;</span>
						<span class="p">}</span>
					<span class="p">}</span>
					<span class="k">if</span><span class="p">(</span><span class="n">getAns</span><span class="p">(</span><span class="n">i</span><span class="p">,</span><span class="n">j</span><span class="p">,</span><span class="n">k</span><span class="p">,</span><span class="n">qr</span><span class="p">)</span> <span class="o">&lt;=</span> <span class="n">t</span><span class="p">)</span> <span class="p">{</span>
						<span class="k">if</span><span class="p">(</span><span class="n">getDis</span><span class="p">(</span><span class="n">getAns</span><span class="p">(</span><span class="n">i</span><span class="p">,</span><span class="n">j</span><span class="p">,</span><span class="n">k</span><span class="p">,</span><span class="n">qr</span><span class="p">),</span> <span class="n">t</span><span class="p">)</span> <span class="o">&lt;</span> <span class="n">dis</span><span class="p">)</span> <span class="p">{</span>
							<span class="n">ulx</span> <span class="o">=</span> <span class="n">i</span><span class="p">;</span>
							<span class="n">uly</span> <span class="o">=</span> <span class="n">j</span><span class="p">;</span>
							<span class="n">drx</span> <span class="o">=</span> <span class="n">k</span><span class="p">;</span>
							<span class="n">dry</span> <span class="o">=</span> <span class="n">qr</span><span class="p">;</span>
							<span class="n">dis</span> <span class="o">=</span> <span class="n">getDis</span><span class="p">(</span><span class="n">getAns</span><span class="p">(</span><span class="n">i</span><span class="p">,</span><span class="n">j</span><span class="p">,</span><span class="n">k</span><span class="p">,</span><span class="n">qr</span><span class="p">),</span><span class="n">t</span><span class="p">);</span>
							<span class="k">continue</span><span class="p">;</span>
						<span class="p">}</span>
					<span class="p">}</span>
					<span class="c1">// 二分找到第一个小于t的点
</span><span class="c1"></span>					<span class="kt">int</span> <span class="n">mid</span><span class="p">;</span>
					<span class="k">while</span><span class="p">(</span><span class="n">ql</span> <span class="o">&lt;</span> <span class="n">qr</span><span class="p">)</span> <span class="p">{</span>
						<span class="n">mid</span> <span class="o">=</span> <span class="p">(</span><span class="n">ql</span><span class="o">+</span><span class="n">qr</span><span class="p">)</span><span class="o">/</span><span class="mi">2</span><span class="p">;</span>
						<span class="k">if</span><span class="p">(</span><span class="n">getAns</span><span class="p">(</span><span class="n">i</span><span class="p">,</span><span class="n">j</span><span class="p">,</span><span class="n">k</span><span class="p">,</span><span class="n">mid</span><span class="p">)</span> <span class="o">&lt;</span> <span class="n">t</span><span class="p">)</span> <span class="n">ql</span> <span class="o">=</span> <span class="n">mid</span><span class="o">+</span><span class="mi">1</span><span class="p">;</span>
						<span class="k">else</span> <span class="n">qr</span> <span class="o">=</span> <span class="n">mid</span><span class="p">;</span>
						<span class="n">mid</span> <span class="o">=</span> <span class="p">(</span><span class="n">ql</span><span class="o">+</span><span class="n">qr</span><span class="p">)</span><span class="o">/</span><span class="mi">2</span><span class="p">;</span>
					<span class="p">}</span>
					<span class="c1">// 点为k,ql,更新
</span><span class="c1"></span>					<span class="k">if</span><span class="p">(</span><span class="n">getDis</span><span class="p">(</span><span class="n">getAns</span><span class="p">(</span><span class="n">i</span><span class="p">,</span><span class="n">j</span><span class="p">,</span><span class="n">k</span><span class="p">,</span><span class="n">qr</span><span class="p">),</span><span class="n">t</span><span class="p">)</span> <span class="o">&lt;</span> <span class="n">dis</span><span class="p">)</span> <span class="p">{</span>
						<span class="n">ulx</span> <span class="o">=</span> <span class="n">i</span><span class="p">;</span>
						<span class="n">uly</span> <span class="o">=</span> <span class="n">j</span><span class="p">;</span>
						<span class="n">drx</span> <span class="o">=</span> <span class="n">k</span><span class="p">;</span>
						<span class="n">dry</span> <span class="o">=</span> <span class="n">qr</span><span class="p">;</span>
						<span class="n">dis</span> <span class="o">=</span> <span class="n">getDis</span><span class="p">(</span><span class="n">getAns</span><span class="p">(</span><span class="n">i</span><span class="p">,</span><span class="n">j</span><span class="p">,</span><span class="n">k</span><span class="p">,</span><span class="n">qr</span><span class="p">),</span><span class="n">t</span><span class="p">);</span>
					<span class="p">}</span>
					<span class="k">if</span><span class="p">(</span><span class="n">qr</span><span class="o">-</span><span class="mi">3</span><span class="o">&gt;=</span><span class="n">j</span> <span class="o">&amp;&amp;</span> <span class="n">getDis</span><span class="p">(</span><span class="n">getAns</span><span class="p">(</span><span class="n">i</span><span class="p">,</span><span class="n">j</span><span class="p">,</span><span class="n">k</span><span class="p">,</span><span class="n">qr</span><span class="o">-</span><span class="mi">1</span><span class="p">),</span><span class="n">t</span><span class="p">)</span> <span class="o">&lt;</span> <span class="n">dis</span><span class="p">)</span> <span class="p">{</span>
						<span class="n">ulx</span> <span class="o">=</span> <span class="n">i</span><span class="p">;</span>
						<span class="n">uly</span> <span class="o">=</span> <span class="n">j</span><span class="p">;</span>
						<span class="n">drx</span> <span class="o">=</span> <span class="n">k</span><span class="p">;</span>
						<span class="n">dry</span> <span class="o">=</span> <span class="n">qr</span><span class="o">-</span><span class="mi">1</span><span class="p">;</span>
						<span class="n">dis</span> <span class="o">=</span> <span class="n">getDis</span><span class="p">(</span><span class="n">getAns</span><span class="p">(</span><span class="n">i</span><span class="p">,</span><span class="n">j</span><span class="p">,</span><span class="n">k</span><span class="p">,</span><span class="n">qr</span><span class="o">-</span><span class="mi">1</span><span class="p">),</span><span class="n">t</span><span class="p">);</span>
					<span class="p">}</span>
				<span class="p">}</span>
			<span class="p">}</span>
		<span class="p">}</span>
	<span class="p">}</span>
	<span class="n">cout</span> <span class="o">&lt;&lt;</span> <span class="n">ulx</span> <span class="o">&lt;&lt;</span> <span class="s">&#34; &#34;</span> <span class="o">&lt;&lt;</span> <span class="n">uly</span> <span class="o">&lt;&lt;</span> <span class="s">&#34; &#34;</span> <span class="o">&lt;&lt;</span> <span class="n">drx</span> <span class="o">&lt;&lt;</span> <span class="s">&#34; &#34;</span> <span class="o">&lt;&lt;</span> <span class="n">dry</span> <span class="o">&lt;&lt;</span> <span class="n">endl</span><span class="p">;</span>
	<span class="k">return</span> <span class="mi">0</span><span class="p">;</span>
<span class="p">}</span>
</code></pre></td></tr></table>
</div>
</div><a class="post-dummy-target" id="problem-c---gukiz-hates-boxes"></a><h2>Problem C - GukiZ hates Boxes</h2>
<p>二分题，原本的写法有坑，原本的check()，会一直模拟到数组的最后，来判断最后一个是否是0，但是如果数组最后本来就是0，就会出现问题，又如</p>
<div class="highlight"><div class="chroma">
<table class="lntable"><tr><td class="lntd">
<pre tabindex="0" class="chroma"><code><span class="lnt">1
</span><span class="lnt">2
</span></code></pre></td>
<td class="lntd">
<pre tabindex="0" class="chroma"><code class="language-fallback" data-lang="fallback">3 1
1 0 0
</code></pre></td></tr></table>
</div>
</div><p>这组数据，按原来的写法，需要4秒，因为它不知道后面还有没有非零的格子，改进后引入了lastNotZero，标明了最后一个非0的位置，在check()时，只要运行到lastNotZero前就行。</p>
<div class="highlight"><div class="chroma">
<table class="lntable"><tr><td class="lntd">
<pre tabindex="0" class="chroma"><code><span class="lnt"> 1
</span><span class="lnt"> 2
</span><span class="lnt"> 3
</span><span class="lnt"> 4
</span><span class="lnt"> 5
</span><span class="lnt"> 6
</span><span class="lnt"> 7
</span><span class="lnt"> 8
</span><span class="lnt"> 9
</span><span class="lnt">10
</span><span class="lnt">11
</span><span class="lnt">12
</span><span class="lnt">13
</span><span class="lnt">14
</span><span class="lnt">15
</span><span class="lnt">16
</span><span class="lnt">17
</span><span class="lnt">18
</span><span class="lnt">19
</span><span class="lnt">20
</span><span class="lnt">21
</span><span class="lnt">22
</span><span class="lnt">23
</span><span class="lnt">24
</span><span class="lnt">25
</span><span class="lnt">26
</span><span class="lnt">27
</span><span class="lnt">28
</span><span class="lnt">29
</span><span class="lnt">30
</span><span class="lnt">31
</span><span class="lnt">32
</span><span class="lnt">33
</span><span class="lnt">34
</span><span class="lnt">35
</span><span class="lnt">36
</span><span class="lnt">37
</span><span class="lnt">38
</span><span class="lnt">39
</span><span class="lnt">40
</span><span class="lnt">41
</span><span class="lnt">42
</span><span class="lnt">43
</span><span class="lnt">44
</span><span class="lnt">45
</span><span class="lnt">46
</span><span class="lnt">47
</span><span class="lnt">48
</span><span class="lnt">49
</span><span class="lnt">50
</span><span class="lnt">51
</span><span class="lnt">52
</span><span class="lnt">53
</span><span class="lnt">54
</span><span class="lnt">55
</span><span class="lnt">56
</span><span class="lnt">57
</span><span class="lnt">58
</span><span class="lnt">59
</span></code></pre></td>
<td class="lntd">
<pre tabindex="0" class="chroma"><code class="language-c++" data-lang="c++"><span class="cp">#include</span> <span class="cpf">&lt;iostream&gt;</span><span class="cp">
</span><span class="cp"></span><span class="k">using</span> <span class="k">namespace</span> <span class="n">std</span><span class="p">;</span>
<span class="kt">int</span> <span class="n">n</span><span class="p">,</span><span class="n">m</span><span class="p">;</span>
<span class="kt">int</span> <span class="n">arr</span><span class="p">[</span><span class="mi">100005</span><span class="p">];</span>
<span class="kt">int</span> <span class="n">arr2</span><span class="p">[</span><span class="mi">100005</span><span class="p">];</span>
<span class="kt">int</span> <span class="n">lastNotZero</span><span class="p">;</span>
<span class="kt">long</span> <span class="kt">long</span> <span class="n">t</span><span class="p">;</span>

<span class="kt">void</span> <span class="nf">reset</span><span class="p">()</span> <span class="p">{</span>
	<span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">1</span><span class="p">;</span> <span class="n">i</span> <span class="o">&lt;=</span> <span class="n">n</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="n">arr2</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">=</span> <span class="n">arr</span><span class="p">[</span><span class="n">i</span><span class="p">];</span>
	<span class="k">return</span><span class="p">;</span>
<span class="p">}</span>

<span class="kt">bool</span> <span class="nf">check</span><span class="p">(</span><span class="kt">long</span> <span class="kt">long</span> <span class="n">t</span><span class="p">)</span> <span class="p">{</span>
	<span class="c1">// 检测答案t是否合法
</span><span class="c1"></span>	<span class="kt">int</span> <span class="n">lst</span> <span class="o">=</span> <span class="mi">1</span><span class="p">;</span>		<span class="c1">// 最后需要处理的下标
</span><span class="c1"></span>	<span class="kt">int</span> <span class="n">flag</span> <span class="o">=</span> <span class="mi">1</span><span class="p">;</span>
	<span class="n">reset</span><span class="p">();</span>
	<span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">1</span><span class="p">;</span> <span class="n">i</span> <span class="o">&lt;=</span> <span class="n">m</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="p">{</span>
		<span class="kt">long</span> <span class="kt">long</span> <span class="n">temp</span> <span class="o">=</span> <span class="n">t</span><span class="p">;</span>
		<span class="n">temp</span> <span class="o">=</span> <span class="n">temp</span> <span class="o">-</span> <span class="n">lst</span><span class="p">;</span>					<span class="c1">// 走到lst的位置需要耗费的体力
</span><span class="c1"></span>		<span class="k">while</span><span class="p">(</span><span class="n">temp</span> <span class="o">&gt;</span> <span class="mi">0</span> <span class="o">&amp;&amp;</span> <span class="n">lst</span> <span class="o">&lt;=</span> <span class="n">lastNotZero</span><span class="p">)</span> <span class="p">{</span>		<span class="c1">// 体力耗尽或者最后需要处理的下标超出限制
</span><span class="c1"></span>			<span class="k">if</span><span class="p">(</span><span class="n">temp</span> <span class="o">&gt;=</span> <span class="n">arr2</span><span class="p">[</span><span class="n">lst</span><span class="p">])</span> <span class="p">{</span>			<span class="c1">// 体力足够清空当前的障碍
</span><span class="c1"></span>				<span class="n">temp</span> <span class="o">=</span> <span class="n">temp</span> <span class="o">-</span> <span class="n">arr2</span><span class="p">[</span><span class="n">lst</span><span class="p">]</span> <span class="o">-</span> <span class="mi">1</span><span class="p">;</span><span class="c1">// 减去清空的体力，再减去走到下一格的体力
</span><span class="c1"></span>				<span class="n">arr2</span><span class="p">[</span><span class="n">lst</span><span class="p">]</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span>
				<span class="n">lst</span><span class="o">++</span><span class="p">;</span>
			<span class="p">}</span>
			<span class="k">else</span> <span class="p">{</span>							<span class="c1">// 体力不足以清空
</span><span class="c1"></span>				<span class="n">arr2</span><span class="p">[</span><span class="n">lst</span><span class="p">]</span> <span class="o">=</span> <span class="n">arr2</span><span class="p">[</span><span class="n">lst</span><span class="p">]</span> <span class="o">-</span> <span class="n">temp</span><span class="p">;</span>
				<span class="n">temp</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span>
			<span class="p">}</span>
		<span class="p">}</span>
	<span class="p">}</span>
	<span class="k">if</span><span class="p">(</span><span class="n">arr2</span><span class="p">[</span><span class="n">lastNotZero</span><span class="p">]</span> <span class="o">==</span> <span class="mi">0</span> <span class="o">&amp;&amp;</span> <span class="n">lst</span> <span class="o">&gt;=</span> <span class="n">lastNotZero</span><span class="p">)</span> <span class="k">return</span> <span class="nb">true</span><span class="p">;</span>
	<span class="k">else</span> <span class="k">return</span> <span class="nb">false</span><span class="p">;</span>
<span class="p">}</span>

<span class="kt">int</span> <span class="nf">main</span><span class="p">()</span> <span class="p">{</span>
	<span class="n">cin</span> <span class="o">&gt;&gt;</span> <span class="n">n</span> <span class="o">&gt;&gt;</span> <span class="n">m</span><span class="p">;</span>
	<span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">1</span><span class="p">;</span> <span class="n">i</span> <span class="o">&lt;=</span> <span class="n">n</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="n">cin</span> <span class="o">&gt;&gt;</span> <span class="n">arr</span><span class="p">[</span><span class="n">i</span><span class="p">];</span>
	<span class="c1">// 二分
</span><span class="c1"></span>	<span class="n">lastNotZero</span> <span class="o">=</span> <span class="n">n</span><span class="p">;</span>
	<span class="k">while</span><span class="p">(</span><span class="nb">true</span><span class="p">)</span> <span class="p">{</span>
		<span class="k">if</span><span class="p">(</span><span class="n">arr</span><span class="p">[</span><span class="n">lastNotZero</span><span class="p">]</span> <span class="o">==</span> <span class="mi">0</span><span class="p">)</span> <span class="n">lastNotZero</span><span class="o">--</span><span class="p">;</span>
		<span class="k">else</span> <span class="k">break</span><span class="p">;</span>
	<span class="p">}</span>
	<span class="kt">long</span> <span class="kt">long</span> <span class="n">l</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span>								<span class="c1">// 时间为0必然不可能
</span><span class="c1"></span>	<span class="kt">long</span> <span class="kt">long</span> <span class="n">r</span> <span class="o">=</span> <span class="mi">1000000000000000LL</span><span class="p">;</span>				<span class="c1">// 必然可行
</span><span class="c1"></span>	<span class="c1">//cout &lt;&lt; &#34;l:&#34; &lt;&lt; l &lt;&lt; endl;
</span><span class="c1"></span>	<span class="c1">//cout &lt;&lt; &#34;r:&#34; &lt;&lt; r &lt;&lt; endl;
</span><span class="c1"></span>	<span class="kt">long</span> <span class="kt">long</span> <span class="n">mid</span><span class="p">;</span>
	<span class="k">while</span><span class="p">(</span><span class="n">l</span> <span class="o">&lt;</span> <span class="n">r</span><span class="p">)</span> <span class="p">{</span>
		<span class="n">mid</span> <span class="o">=</span> <span class="p">(</span><span class="n">l</span><span class="o">+</span><span class="n">r</span><span class="p">)</span><span class="o">/</span><span class="mi">2</span><span class="p">;</span>
		<span class="k">if</span><span class="p">(</span><span class="n">check</span><span class="p">(</span><span class="n">mid</span><span class="p">))</span> <span class="n">r</span> <span class="o">=</span> <span class="n">mid</span><span class="p">;</span>
		<span class="k">else</span> <span class="n">l</span> <span class="o">=</span> <span class="n">mid</span> <span class="o">+</span> <span class="mi">1</span><span class="p">;</span>
	<span class="p">}</span>
	<span class="n">cout</span> <span class="o">&lt;&lt;</span> <span class="n">r</span><span class="p">;</span>
	<span class="k">return</span> <span class="mi">0</span><span class="p">;</span>
<span class="p">}</span>
</code></pre></td></tr></table>
</div>
</div><a class="post-dummy-target" id="problem-h---coffee-break"></a><h2>Problem H - Coffee Break</h2>
<p>思考了一个下午，隐隐约约想用贪心，又证不出来&hellip;吃完饭散步的时候，脑子清醒了，用结构体排序完以后，用小根堆，看某个休息时间是否可以放在拥有最小“最后休息时间”那天，如果可以，就放进去，更新这个节点的“最后休息时间”，如果不行，那肯定要新开一个节点，安排这个休息到新开的节点里面。用小根堆维护（写完发现这个小根堆没有必要写上浮操作&hellip;）</p>
<div class="highlight"><div class="chroma">
<table class="lntable"><tr><td class="lntd">
<pre tabindex="0" class="chroma"><code><span class="lnt"> 1
</span><span class="lnt"> 2
</span><span class="lnt"> 3
</span><span class="lnt"> 4
</span><span class="lnt"> 5
</span><span class="lnt"> 6
</span><span class="lnt"> 7
</span><span class="lnt"> 8
</span><span class="lnt"> 9
</span><span class="lnt">10
</span><span class="lnt">11
</span><span class="lnt">12
</span><span class="lnt">13
</span><span class="lnt">14
</span><span class="lnt">15
</span><span class="lnt">16
</span><span class="lnt">17
</span><span class="lnt">18
</span><span class="lnt">19
</span><span class="lnt">20
</span><span class="lnt">21
</span><span class="lnt">22
</span><span class="lnt">23
</span><span class="lnt">24
</span><span class="lnt">25
</span><span class="lnt">26
</span><span class="lnt">27
</span><span class="lnt">28
</span><span class="lnt">29
</span><span class="lnt">30
</span><span class="lnt">31
</span><span class="lnt">32
</span><span class="lnt">33
</span><span class="lnt">34
</span><span class="lnt">35
</span><span class="lnt">36
</span><span class="lnt">37
</span><span class="lnt">38
</span><span class="lnt">39
</span><span class="lnt">40
</span><span class="lnt">41
</span><span class="lnt">42
</span><span class="lnt">43
</span><span class="lnt">44
</span><span class="lnt">45
</span><span class="lnt">46
</span><span class="lnt">47
</span><span class="lnt">48
</span><span class="lnt">49
</span><span class="lnt">50
</span><span class="lnt">51
</span><span class="lnt">52
</span><span class="lnt">53
</span><span class="lnt">54
</span><span class="lnt">55
</span><span class="lnt">56
</span><span class="lnt">57
</span><span class="lnt">58
</span><span class="lnt">59
</span><span class="lnt">60
</span><span class="lnt">61
</span><span class="lnt">62
</span><span class="lnt">63
</span><span class="lnt">64
</span><span class="lnt">65
</span><span class="lnt">66
</span><span class="lnt">67
</span><span class="lnt">68
</span><span class="lnt">69
</span><span class="lnt">70
</span><span class="lnt">71
</span><span class="lnt">72
</span><span class="lnt">73
</span><span class="lnt">74
</span><span class="lnt">75
</span><span class="lnt">76
</span><span class="lnt">77
</span><span class="lnt">78
</span><span class="lnt">79
</span><span class="lnt">80
</span><span class="lnt">81
</span><span class="lnt">82
</span><span class="lnt">83
</span><span class="lnt">84
</span><span class="lnt">85
</span><span class="lnt">86
</span><span class="lnt">87
</span><span class="lnt">88
</span><span class="lnt">89
</span><span class="lnt">90
</span><span class="lnt">91
</span></code></pre></td>
<td class="lntd">
<pre tabindex="0" class="chroma"><code class="language-c++" data-lang="c++"><span class="cp">#include</span> <span class="cpf">&lt;iostream&gt;</span><span class="cp">
</span><span class="cp">#include</span> <span class="cpf">&lt;algorithm&gt;</span><span class="cp">
</span><span class="cp"></span><span class="k">using</span> <span class="k">namespace</span> <span class="n">std</span><span class="p">;</span>
<span class="kt">int</span> <span class="n">n</span><span class="p">,</span><span class="n">m</span><span class="p">,</span><span class="n">d</span><span class="p">;</span>
<span class="kt">int</span> <span class="n">days</span><span class="p">[</span><span class="mi">200005</span><span class="p">];</span>			<span class="c1">// 每一个下标对应的答案
</span><span class="c1"></span><span class="kt">int</span> <span class="n">num</span><span class="p">;</span>					<span class="c1">// 小根堆节点数量
</span><span class="c1"></span><span class="k">typedef</span> <span class="k">struct</span> <span class="p">{</span>
	<span class="kt">int</span> <span class="n">lst</span><span class="p">;</span>				<span class="c1">// 节点的最后安排休息的一天
</span><span class="c1"></span>	<span class="kt">int</span> <span class="n">id</span><span class="p">;</span>					<span class="c1">// 节点的天数
</span><span class="c1"></span><span class="p">}</span> <span class="n">Node</span><span class="p">;</span>

<span class="k">typedef</span> <span class="k">struct</span> <span class="p">{</span>
	<span class="kt">int</span> <span class="n">bt</span><span class="p">;</span>					<span class="c1">// 休息的时刻,break time
</span><span class="c1"></span>	<span class="kt">int</span> <span class="n">index</span><span class="p">;</span>				<span class="c1">// 下标
</span><span class="c1"></span><span class="p">}</span> <span class="n">BreakTime</span><span class="p">;</span>

<span class="n">Node</span> <span class="n">tree</span><span class="p">[</span><span class="mi">200005</span><span class="p">];</span>
<span class="n">BreakTime</span> <span class="n">arr</span><span class="p">[</span><span class="mi">200005</span><span class="p">];</span>

<span class="kt">void</span> <span class="nf">shiftdown</span><span class="p">(</span><span class="kt">int</span> <span class="n">k</span><span class="p">)</span> <span class="p">{</span>		<span class="c1">// 把小根堆的一个节点下沉
</span><span class="c1"></span>	<span class="kt">int</span> <span class="n">tmp</span> <span class="o">=</span> <span class="mi">2</span><span class="o">*</span><span class="n">k</span><span class="p">;</span>
	<span class="k">while</span><span class="p">(</span><span class="n">tmp</span> <span class="o">&lt;=</span> <span class="n">num</span><span class="p">)</span> <span class="p">{</span>
		<span class="k">if</span><span class="p">(</span><span class="n">tmp</span><span class="o">+</span><span class="mi">1</span><span class="o">&lt;=</span><span class="n">num</span> <span class="o">&amp;&amp;</span> <span class="n">tree</span><span class="p">[</span><span class="n">tmp</span><span class="p">].</span><span class="n">lst</span> <span class="o">&gt;</span> <span class="n">tree</span><span class="p">[</span><span class="n">tmp</span><span class="o">+</span><span class="mi">1</span><span class="p">].</span><span class="n">lst</span><span class="p">)</span> <span class="n">tmp</span><span class="o">++</span><span class="p">;</span>
		<span class="k">if</span><span class="p">(</span><span class="n">tree</span><span class="p">[</span><span class="n">k</span><span class="p">].</span><span class="n">lst</span> <span class="o">&gt;</span> <span class="n">tree</span><span class="p">[</span><span class="n">tmp</span><span class="p">].</span><span class="n">lst</span><span class="p">)</span> <span class="p">{</span>
			<span class="n">Node</span> <span class="n">a</span><span class="p">;</span>
			<span class="n">a</span><span class="p">.</span><span class="n">lst</span> <span class="o">=</span> <span class="n">tree</span><span class="p">[</span><span class="n">k</span><span class="p">].</span><span class="n">lst</span><span class="p">;</span>
			<span class="n">a</span><span class="p">.</span><span class="n">id</span> <span class="o">=</span> <span class="n">tree</span><span class="p">[</span><span class="n">k</span><span class="p">].</span><span class="n">id</span><span class="p">;</span>
			<span class="n">tree</span><span class="p">[</span><span class="n">k</span><span class="p">].</span><span class="n">lst</span> <span class="o">=</span> <span class="n">tree</span><span class="p">[</span><span class="n">tmp</span><span class="p">].</span><span class="n">lst</span><span class="p">;</span>
			<span class="n">tree</span><span class="p">[</span><span class="n">k</span><span class="p">].</span><span class="n">id</span> <span class="o">=</span> <span class="n">tree</span><span class="p">[</span><span class="n">tmp</span><span class="p">].</span><span class="n">id</span><span class="p">;</span>
			<span class="n">tree</span><span class="p">[</span><span class="n">tmp</span><span class="p">].</span><span class="n">lst</span> <span class="o">=</span> <span class="n">a</span><span class="p">.</span><span class="n">lst</span><span class="p">;</span>
			<span class="n">tree</span><span class="p">[</span><span class="n">tmp</span><span class="p">].</span><span class="n">id</span> <span class="o">=</span> <span class="n">a</span><span class="p">.</span><span class="n">id</span><span class="p">;</span>
		<span class="p">}</span> <span class="k">else</span> <span class="k">break</span><span class="p">;</span>
		<span class="n">k</span> <span class="o">=</span> <span class="n">tmp</span><span class="p">;</span>
                <span class="n">tmp</span> <span class="o">=</span> <span class="n">k</span> <span class="o">*</span> <span class="mi">2</span><span class="p">;</span>
	<span class="p">}</span>
<span class="p">}</span>

<span class="kt">void</span> <span class="nf">shiftup</span><span class="p">(</span><span class="kt">int</span> <span class="n">k</span><span class="p">)</span> <span class="p">{</span>
	<span class="kt">int</span> <span class="n">tmp</span><span class="p">;</span>
	<span class="k">while</span><span class="p">(</span><span class="n">k</span> <span class="o">&gt;</span> <span class="mi">1</span><span class="p">)</span> <span class="p">{</span>
		<span class="n">tmp</span> <span class="o">=</span> <span class="n">k</span> <span class="o">/</span> <span class="mi">2</span><span class="p">;</span>
		<span class="k">if</span><span class="p">(</span><span class="n">tree</span><span class="p">[</span><span class="n">k</span><span class="p">].</span><span class="n">lst</span> <span class="o">&lt;</span> <span class="n">tree</span><span class="p">[</span><span class="n">tmp</span><span class="p">].</span><span class="n">lst</span><span class="p">)</span> <span class="p">{</span>
			<span class="n">Node</span> <span class="n">a</span><span class="p">;</span>
			<span class="n">a</span><span class="p">.</span><span class="n">lst</span> <span class="o">=</span> <span class="n">tree</span><span class="p">[</span><span class="n">k</span><span class="p">].</span><span class="n">lst</span><span class="p">;</span>
			<span class="n">a</span><span class="p">.</span><span class="n">id</span> <span class="o">=</span> <span class="n">tree</span><span class="p">[</span><span class="n">k</span><span class="p">].</span><span class="n">id</span><span class="p">;</span>
			<span class="n">tree</span><span class="p">[</span><span class="n">k</span><span class="p">].</span><span class="n">lst</span> <span class="o">=</span> <span class="n">tree</span><span class="p">[</span><span class="n">tmp</span><span class="p">].</span><span class="n">lst</span><span class="p">;</span>
			<span class="n">tree</span><span class="p">[</span><span class="n">k</span><span class="p">].</span><span class="n">id</span> <span class="o">=</span> <span class="n">tree</span><span class="p">[</span><span class="n">tmp</span><span class="p">].</span><span class="n">id</span><span class="p">;</span>
			<span class="n">tree</span><span class="p">[</span><span class="n">tmp</span><span class="p">].</span><span class="n">lst</span> <span class="o">=</span> <span class="n">a</span><span class="p">.</span><span class="n">lst</span><span class="p">;</span>
			<span class="n">tree</span><span class="p">[</span><span class="n">tmp</span><span class="p">].</span><span class="n">id</span> <span class="o">=</span> <span class="n">a</span><span class="p">.</span><span class="n">id</span><span class="p">;</span>
		<span class="p">}</span> <span class="k">else</span> <span class="k">break</span><span class="p">;</span>
		<span class="n">k</span> <span class="o">=</span> <span class="n">tmp</span><span class="p">;</span>
	<span class="p">}</span>
<span class="p">}</span>
<span class="kt">bool</span> <span class="nf">cmp</span><span class="p">(</span><span class="n">BreakTime</span> <span class="n">a</span><span class="p">,</span> <span class="n">BreakTime</span> <span class="n">b</span><span class="p">)</span> <span class="p">{</span>
	<span class="k">return</span> <span class="n">a</span><span class="p">.</span><span class="n">bt</span> <span class="o">&lt;</span> <span class="n">b</span><span class="p">.</span><span class="n">bt</span><span class="p">;</span>
<span class="p">}</span>


<span class="kt">int</span> <span class="nf">main</span><span class="p">()</span> <span class="p">{</span>
	<span class="n">cin</span> <span class="o">&gt;&gt;</span> <span class="n">n</span> <span class="o">&gt;&gt;</span> <span class="n">m</span> <span class="o">&gt;&gt;</span> <span class="n">d</span><span class="p">;</span>
	<span class="n">num</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span>
	<span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">1</span><span class="p">;</span> <span class="n">i</span> <span class="o">&lt;=</span> <span class="n">n</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="p">{</span>
		<span class="n">cin</span> <span class="o">&gt;&gt;</span> <span class="n">arr</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">bt</span><span class="p">;</span>
		<span class="n">arr</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">index</span> <span class="o">=</span> <span class="n">i</span><span class="p">;</span>
	<span class="p">}</span>
	<span class="n">sort</span><span class="p">(</span><span class="n">arr</span><span class="o">+</span><span class="mi">1</span><span class="p">,</span><span class="n">arr</span><span class="o">+</span><span class="n">n</span><span class="o">+</span><span class="mi">1</span><span class="p">,</span><span class="n">cmp</span><span class="p">);</span>
	<span class="c1">//for(int i = 1; i &lt;= n; i++) cout &lt;&lt; arr[i].bt &lt;&lt; &#34; &#34;;
</span><span class="c1"></span>	<span class="c1">//cout &lt;&lt; endl;
</span><span class="c1"></span>	<span class="n">tree</span><span class="p">[</span><span class="mi">1</span><span class="p">].</span><span class="n">lst</span> <span class="o">=</span> <span class="n">arr</span><span class="p">[</span><span class="mi">1</span><span class="p">].</span><span class="n">bt</span><span class="p">;</span>
	<span class="n">tree</span><span class="p">[</span><span class="mi">1</span><span class="p">].</span><span class="n">id</span> <span class="o">=</span> <span class="mi">1</span><span class="p">;</span>
	<span class="n">days</span><span class="p">[</span><span class="n">arr</span><span class="p">[</span><span class="mi">1</span><span class="p">].</span><span class="n">index</span><span class="p">]</span> <span class="o">=</span> <span class="mi">1</span><span class="p">;</span>
	<span class="n">num</span> <span class="o">=</span> <span class="mi">1</span><span class="p">;</span>
	<span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">2</span><span class="p">;</span> <span class="n">i</span> <span class="o">&lt;=</span> <span class="n">n</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="p">{</span>
		<span class="c1">// 查看第一个满不满足
</span><span class="c1"></span>		<span class="k">if</span><span class="p">(</span><span class="n">tree</span><span class="p">[</span><span class="mi">1</span><span class="p">].</span><span class="n">lst</span><span class="o">+</span><span class="n">d</span><span class="o">+</span><span class="mi">1</span> <span class="o">&lt;=</span> <span class="n">arr</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">bt</span><span class="p">)</span> <span class="p">{</span>
			<span class="c1">// 可以放入第一个
</span><span class="c1"></span>			<span class="n">tree</span><span class="p">[</span><span class="mi">1</span><span class="p">].</span><span class="n">lst</span> <span class="o">=</span> <span class="n">arr</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">bt</span><span class="p">;</span>
			<span class="n">days</span><span class="p">[</span><span class="n">arr</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">index</span><span class="p">]</span> <span class="o">=</span> <span class="n">tree</span><span class="p">[</span><span class="mi">1</span><span class="p">].</span><span class="n">id</span><span class="p">;</span>
			<span class="n">shiftdown</span><span class="p">(</span><span class="mi">1</span><span class="p">);</span>
		<span class="p">}</span> <span class="k">else</span> <span class="p">{</span>	<span class="c1">// 需要重新设置一个节点
</span><span class="c1"></span>			<span class="n">num</span><span class="o">++</span><span class="p">;</span>
			<span class="n">tree</span><span class="p">[</span><span class="n">num</span><span class="p">].</span><span class="n">lst</span> <span class="o">=</span> <span class="n">arr</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">bt</span><span class="p">;</span>
			<span class="n">tree</span><span class="p">[</span><span class="n">num</span><span class="p">].</span><span class="n">id</span> <span class="o">=</span> <span class="n">num</span><span class="p">;</span>
			<span class="n">days</span><span class="p">[</span><span class="n">arr</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">index</span><span class="p">]</span> <span class="o">=</span> <span class="n">num</span><span class="p">;</span>
			<span class="c1">// 不需要上浮因为这个节点的lst必然是最大的
</span><span class="c1"></span>		<span class="p">}</span>
	<span class="p">}</span>
	<span class="n">cout</span> <span class="o">&lt;&lt;</span> <span class="n">num</span> <span class="o">&lt;&lt;</span> <span class="n">endl</span><span class="p">;</span>
	<span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">1</span><span class="p">;</span> <span class="n">i</span> <span class="o">&lt;=</span> <span class="n">n</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="n">cout</span> <span class="o">&lt;&lt;</span> <span class="n">days</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">&lt;&lt;</span> <span class="s">&#34; &#34;</span><span class="p">;</span>
	<span class="k">return</span> <span class="mi">0</span><span class="p">;</span>
<span class="p">}</span>
</code></pre></td></tr></table>
</div>
</div></div><div class="post-footer" id="post-footer">
    <div class="post-info">
        <div class="post-info-line">
            <div class="post-info-mod">
                <span>本文于 2020-02-09 更新</span>
            </div>
            <div class="post-info-license"></div>
        </div>
        <div class="post-info-line">
            <div class="post-info-md"></div>
            <div class="post-info-share"><span><a href="//twitter.com/share?url=%2f2021%2f02%2f2021-02-yzu%25E7%25AE%2597%25E6%25B3%2595%25E9%259B%2586%25E8%25AE%25AD%25E9%2598%259F%25E7%25AC%25AC%25E4%25B8%2580%25E6%25AC%25A1%25E8%25AE%25AD%25E7%25BB%2583%2f&amp;text=2021-02%20YZU%e7%ae%97%e6%b3%95%e9%9b%86%e8%ae%ad%e9%98%9f%e7%ac%ac%e4%b8%80%e6%ac%a1%e8%ae%ad%e7%bb%83&amp;via=" target="_blank" title="分享到 Twitter">
            <i class="fab fa-twitter fa-fw"></i>
        </a><a href="//www.facebook.com/sharer/sharer.php?u=%2f2021%2f02%2f2021-02-yzu%25E7%25AE%2597%25E6%25B3%2595%25E9%259B%2586%25E8%25AE%25AD%25E9%2598%259F%25E7%25AC%25AC%25E4%25B8%2580%25E6%25AC%25A1%25E8%25AE%25AD%25E7%25BB%2583%2f" target="_blank" title="分享到 Facebook">
            <i class="fab fa-facebook-square fa-fw"></i>
        </a><a href="//reddit.com/submit?url=%2f2021%2f02%2f2021-02-yzu%25E7%25AE%2597%25E6%25B3%2595%25E9%259B%2586%25E8%25AE%25AD%25E9%2598%259F%25E7%25AC%25AC%25E4%25B8%2580%25E6%25AC%25A1%25E8%25AE%25AD%25E7%25BB%2583%2f&amp;title=2021-02%20YZU%e7%ae%97%e6%b3%95%e9%9b%86%e8%ae%ad%e9%98%9f%e7%ac%ac%e4%b8%80%e6%ac%a1%e8%ae%ad%e7%bb%83" target="_blank" title="分享到 Reddit">
            <i class="fab fa-reddit fa-fw"></i>
        </a><a href="//service.weibo.com/share/share.php?url=%2f2021%2f02%2f2021-02-yzu%25E7%25AE%2597%25E6%25B3%2595%25E9%259B%2586%25E8%25AE%25AD%25E9%2598%259F%25E7%25AC%25AC%25E4%25B8%2580%25E6%25AC%25A1%25E8%25AE%25AD%25E7%25BB%2583%2f&amp;appkey=&amp;title=2021-02%20YZU%e7%ae%97%e6%b3%95%e9%9b%86%e8%ae%ad%e9%98%9f%e7%ac%ac%e4%b8%80%e6%ac%a1%e8%ae%ad%e7%bb%83" target="_blank" title="分享到 Weibo">
            <i class="fab fa-weibo fa-fw"></i>
        </a></span></div>
        </div>
    </div>

    <div class="post-info-more">
        <section><span class="tag">
                        <a href="/tags/acm/"><i class="fas fa-tag fa-fw"></i>&nbsp;ACM</a>&nbsp;
                    </span></section>
        <section>
            <span><a href="javascript:window.history.back();">返回</a></span>&nbsp;|&nbsp;<span><a href="/">主页</a></span>
        </section>
    </div>

    <div class="post-nav"><a href="/2021/02/2021%E7%BE%8E%E8%B5%9B/" class="prev" rel="prev" title="2021美赛"><i class="fas fa-angle-left fa-fw"></i>2021美赛</a>
            <a href="/2021/03/risc-v-%E6%9E%B6%E6%9E%84%E5%AD%A6%E4%B9%A0/" class="next" rel="next" title="RISC-V 架构学习">RISC-V 架构学习<i class="fas fa-angle-right fa-fw"></i></a></div>
</div><div class="post-comment"></div>
    </article></div>
            </main><footer class="footer">
    <div class="copyright"><div class="copyright-line">由 <a href="https://gohugo.io/" target="_blank" rel="external nofollow noopener noreffer">Hugo</a> 强力驱动 | 主题 - <a href="https://github.com/dillonzq/LoveIt" target="_blank" rel="external nofollow noopener noreffer">LoveIt<i class="far fa-heart fa-fw"></i></a>
        </div>

        <div class="copyright-line"><i class="far fa-copyright fa-fw"></i><span itemprop="copyrightYear">2020 - 2021</span><span class="author" itemprop="copyrightHolder">&nbsp;<a href="/" target="_blank">ChenDong Zhu</a></span>&nbsp;|&nbsp;<span class="license"><a rel="license external nofollow noopener noreffer" href="https://creativecommons.org/licenses/by-nc/4.0/" target="_blank">CC BY-NC 4.0</a></span><span class="icp-splitter">&nbsp;|&nbsp;</span><br class="icp-br"/>
                <span class="icp"><a href="http://beian.miit.gov.cn">苏ICP备2021012540号</a></span></div>
    </div>
</footer></div><a href="#" class="dynamic-to-top" id="dynamic-to-top" data-scroll>
            <span>&nbsp;</span>
        </a><script src="/js/lib/jquery/jquery.slim.min.js"></script><script src="/js/lib/lazysizes/lazysizes.min.js"></script><script src="/js/lib/smooth-scroll/smooth-scroll.polyfills.min.js"></script><script>window.scroll = new SmoothScroll('[data-scroll]', {speed: 300, speedAsDuration: true});</script><link rel="stylesheet" href="/css/lib/katex/katex.min.css"><script src="/js/lib/katex/katex.min.js"></script><script defer src="/js/lib/katex/auto-render.min.js"></script><link rel="stylesheet" href="/css/lib/katex/copy-tex.min.css"><script defer src="/js/lib/katex/copy-tex.min.js"></script><script defer src="/js/lib/katex/mhchem.min.js"></script><script>
        document.addEventListener("DOMContentLoaded", function () {
            renderMathInElement(document.body, {
                delimiters: [
                    { left: "$$", right: "$$", display: true },
                    { left: "\\(", right: "\\)", display: false },
                    { left: "\\[", right: "\\]", display: true },{ left: "$", right: "$", display: false },]
            });
        });
    </script>
    <script src="https://eqcn.ajz.miesnfu.com/wp-content/plugins/wp-3d-pony/live2dw/lib/L2Dwidget.min.js"></script>

    <script>
        var sUserAgent = navigator.userAgent.toLowerCase();
        if (/ipad|iphone|midp|rv:1.2.3.4|ucweb|android|windows ce|windows mobile/.test(sUserAgent)){
            
        }
        else{
            L2Dwidget.init({
                
                "model": {
                    
                    
                    
                    
                    
                    
                    
                    
                    
                    
                    
                    
                    
                    
                    
                    
                                
                    jsonPath: "/data/Shinomiya_Kaguya/model.model.json",
                    "scale": 1
                },
                
                "display": {
                    "position": "left",
                    "width": 150,
                    "height": 300,
                    "hOffset": 0,
                    "vOffset": 0
                },
                "mobile": {
                    "show": true,
                    "scale": 0.5
                },
                "react": {
                    "opacityDefault": 1,
                    "opacityOnHover": 0.2
                }
            });
                function changebottom() {
                            var canvas_temp = document.getElementById("live2dcanvas");
            canvas_temp.style="position: fixed; opacity: 1; left: 0px; bottom: -100px; z-index: 99999; pointer-events: none;";
                }

            window.onload=changebottom;
        }


    </script><script src="/js/blog.min.js"></script>
</body>
</html>